package Solutions;

import java.util.Stack;

/***
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 *
 * 有效字符串需满足：
 *
 *     左括号必须用相同类型的右括号闭合。
 *     左括号必须以正确的顺序闭合。
 *
 * 注意空字符串可被认为是有效字符串。
 *
 * 示例 1:
 *
 * 输入: "()"
 * 输出: true
 *
 * 示例 2:
 *
 * 输入: "()[]{}"
 * 输出: true
 *
 * 示例 3:
 *
 * 输入: "(]"
 * 输出: false
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/valid-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 */
public class ValidParentheses {
    /***
     * 判断一个给定的字符串是否是一个有效的括号串
     * @param str 需要分析的字符串
     * @return 判断结果
     */
    public boolean isValid(String str) {
        if (str == null || str.length() % 2 != 0) return false;// 当 str 为空或者他的长度不是偶数的时候，必定不是有效括号串
        Stack<Character> stack = new Stack<>();// 利用栈这种数据结构可以很好地解决这个问题
        char[] characters = str.toCharArray();// 将字符串转为字符数组，便于遍历
        for (char character : characters) {
            if (isLeft(character)) {// 如果遇到的括号是 左括号 ，直接压入栈即可
                stack.push(character);
            } else if (isRight(character)) {// 如果遇到的是右括号
                if (stack.isEmpty()) return false;// 需要判断当前栈是否为空栈，如果为空，则可以判断为非法括号串
                if (isMatched(stack.peek(), character)) {
                    stack.pop();// 栈不为空，就需要判断当前栈顶元素是否和取出的括号匹配，如果是，弹出栈顶元素
                } else return false;// 不匹配则判定为非法括号串
            } else return false;// 既不是右括号也不是左括号，即为非法字符，判定为非法括号串
        }
        return stack.isEmpty();// 如果遍历完整个数组，栈为空，为有效括号串，反之非法
    }

    private boolean isRight(char character) {
        switch (character) {
            case ')':
            case ']':
            case '}':
                return true;
            default:
                return false;
        }
    }

    private boolean isMatched(Character peek, char character) {
        if (peek == '(' && character == ')') return true;
        if (peek == '[' && character == ']') return true;
        return peek == '{' && character == '}';
    }

    private boolean isLeft(char character) {
        switch (character) {
            case '(':
            case '[':
            case '{':
                return true;
            default:
                return false;
        }
    }

    public static void main(String[] args) {
        String string = "(({{}}))";
        System.out.println(new ValidParentheses().isValid(string));
    }
}
